package com.cby.leetcode.二分查找.LC2563;

import java.util.Arrays;

/**
 * 二分查找：lowBound
 *
 * 对于递增整数，转为数对 1. >= 直接调
 *                    2. <= 转为 > x 前一位 再转为 >= x + 1 前一位
 *
 * a + b 相加 >= x    转为    a  >= x - b    <= 经过转化同理
 * 因此问题转为遍历右边界，0为恒定左边界，二元转一元
 *
 */


public class LC2563 {

    public static void main(String[] args){

    }

}

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;

        //遍历右边界，在0到j-1找值满足范围，二维转一维
        for (int j = 1; j < nums.length; j++){
            int n  = lowBound(nums, j - 1, upper - nums[j] + 1) - 1 - lowBound(nums, j - 1,lower - nums[j]) + 1;
            if(n > 0)
                ans += n;
        }

        return ans;
    }

    public int lowBound(int nums[],int right,int target){
        int left = 0;

        while(left <= right){
            int mid = (left + right) >>> 1;
            if(nums[mid] >= target)
                right = mid - 1;
            else
                left = mid + 1;
        }

        return left;

    }

}
